// 二分查找递归版 来源网络
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1; 
        } else {
            right = mid - 1; 
        }
    }

    return -1;
}

// arr 短的
function test(arr1:number[],arr2:number[],v:number) : boolean {
    if(!arr1?.length || !arr2?.length) return false;
    return !!arr1.find(a => arr2.find(b => b + a == v));
}

// arr长的 O(N)
function test2(arr1:number[],arr2:number[],v:number) : boolean {
    if(!arr1?.length || !arr2?.length) return false;
    arr1 = arr1.sort();arr2 = arr2.sort();
    
    return !!arr1.find(a => -1 != binarySearch(arr2,v - a));
}

// arr长的 O(1) 空间复杂度O(1)
function test3(arr1:number[],arr2:number[],v:number) : boolean {
    if(!arr1?.length || !arr2?.length) return false;
    let m = new Map();
    arr2.forEach(a => m.set(a,1));
    
    return !!arr1.find(a => m.get(v - a) === 1);
}
